import java.io.*;
import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val=x;
        next=null;
    }
}

public class AddTwoNumbers {

    public static ListNode addTwoNumbers(ListNode l1,ListNode l2) {

        if(l1==null) return l2;
        if(l2==null) return l1;

        int listOneLength = 0;
        int listTwoLength = 0;
        ListNode p = l1;

        ListNode minList = l1;
        ListNode maxList = l2;

        while (p!=null){
            listOneLength++;
            p = p.next;
        }

        p = l2;

        while (p!=null){
            listTwoLength++;
            p = p.next;
        }

        if(listOneLength > listTwoLength) {
            minList = l2;
            maxList = l1;
        }

        p = minList;
        ListNode p1 = maxList;

        while(p!=null){
            p1.val += p.val;
            p1=p1.next;
            p = p.next;
        }

        p1 = maxList;

        while(p1.next != null){
            if(p1.val >= 10){
                p1.next.val += p1.val/10;
                p1.val %= 10;                
            }
            p1 = p1.next;
        }

        if(p1.val >= 10) {
            p1.next = new ListNode(0);
            p1.next.val = p1.val/10;            
            p1.val %= 10;
        }

        return maxList;
    }
    
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(9);
        list.add(9);
        list.add(9);
        list.add(9);
        list.add(9);

        ListNode l1 = new ListNode(9);
        ListNode l2 = new ListNode(9);        
        ListNode pHead1 = l1;
        ListNode pHead2 = l2;        
        
        for(int i=0;i<list.size();i++){
            ListNode p1 = new ListNode(list.get(i));
            pHead1.next = p1;
            pHead1 = p1;

            if(i<=2) {
                ListNode p2 = new ListNode(list.get(i));                        
                pHead2.next = p2;
                pHead2 = p2;
            }
        }

        printListNode(l1);
        System.out.println("============================");
        printListNode(l2);
        System.out.println("============================");

        ListNode listNode = addTwoNumbers(l1,l2);

        printListNode(listNode);
    }

    public static void printListNode(ListNode listNode) {
        while(listNode!=null){
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }
}